/**
* SparseVector 用于表示一个稀疏向量.在初始化SparseVector时,需指明"0"元素.所有的
* "0"元素只会被存储一份.其余非零元素都会被存储.在索引元素值时,效率大概为log(N),N为
* 非零元素的个数.
* 存储空间: N*(sizeof(element)+ sieof(int)), N为非零元素的个数.
* 接口与普通vector类似.
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15-11.21
*/
#pragma once

#include "stdafx.h"

using namespace std;

template<class T>
class SparseVector
{
	vector<T> m_Vec;
	vector<unsigned> m_Index;
	T m_ZeroVal;
	unsigned m_Length;

	int biSearch(const unsigned pos)const;

	//for serialization
	friend class boost::serialization::access;
	template<class Archive>
	void serialize(Archive & ar, const unsigned int version)
	{
		ar & m_Vec;
		ar & m_Index;
		ar & m_ZeroVal;
		ar & m_Length;
	}

public:
	SparseVector();
	SparseVector(const T & v);
	SparseVector(const T & v, const vector<T> & vec);
	SparseVector(const T & v, const unsigned length, const T[]);
	SparseVector(const SparseVector & sv);
	~SparseVector();

	SparseVector<T> & operator = (const SparseVector<T> & sv);

	void toVector(vector<T> & v)const;

	inline unsigned size() const;
	inline bool empty() const;

	const T & front()const;
	const T & back()const;
	const T & at(const unsigned index)const;

	inline unsigned nzSize()const;
	inline const unsigned nzIndex(unsigned pos)const;
	inline const T & nzValue(unsigned pos)const;

	void push_back(const T &);
	void pop_back();
	void insert(const unsigned pos, const T &);
	void erase(const unsigned pos);
	void erase(const unsigned start, const unsigned end);
	void set(const unsigned pos, const T &);
	void update(const unsigned pos, const T &);

	void resize(const unsigned num);
	inline void clear();

	//////////////////////////////////////////////////////////////////////////
	void self_check();
	void show();
};



template<class T>
SparseVector<T>::SparseVector():  m_Length(0)
{
	;
}


/**
* Function: 构造函数,创建一个空的,v为"0"元素的稀疏向量.
* Params: v: 设定v为0元素
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-17
*/
template<class T>
SparseVector<T>::SparseVector(const T & v)
	: m_ZeroVal(v), m_Length(0) {}


/**
* Function: 构造函数,创建一个v为"0"元素的稀疏向量,用vec来初始化这个稀疏向量.
* Params: v: 设定v为0元素; vec: 稀疏向量中每一维的值.
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-17
*/
template<class T>
SparseVector<T>::SparseVector(const T & v, const vector<T> & vec)
	: m_ZeroVal(v), m_Length(vec.size())
{
	for(unsigned i = 0; i < vec.size(); ++i)
	{
		if(vec[i] != v)
		{
			m_Vec.push_back(vec[i]);
			m_Index.push_back(i);
		}
	}
}


/**
* Function: 构造函数,创建一个v为"0"元素的稀疏向量,用vec来初始化这个稀疏向量.
* Params: v: 设定v为0元素; length: 稀疏向量的长度; vec: 稀疏向量中每一维的值.
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-17
*/
template<class T>
SparseVector<T>::SparseVector(const T & v, unsigned length, const T vec[])
	: m_ZeroVal(v), m_Length(length)
{
	for(unsigned i = 0; i < length; ++i)
	{
		if(vec[i] != v)
		{
			m_Vec.push_back(vec[i]);
			m_Index.push_back(i);
		}
	}
}


/**
* Function: 拷贝构造函数
* Params: sv
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-17
*/
template<class T>
SparseVector<T>::SparseVector(const SparseVector & sv)
	: m_ZeroVal(sv.m_ZeroVal), m_Length(sv.m_Length),
	  m_Index(sv.m_Index), m_Vec(sv.m_Vec) {}

/**
* Function: 析构函数
* Params: sv
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-17
*/
template<class T>
SparseVector<T>::~SparseVector() {}

/**
* Function: 重载赋值操作(=)
* Params: sv
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-17
*/
template<class T>
SparseVector<T> & SparseVector<T>::operator = (const SparseVector<T> & sv)
{
	m_Length = sv.m_Length;
	m_Index = sv.m_Index;
	m_Vec = sv.m_Vec;
	return *this;
}

/**
* Function: 将该稀疏向量转换为对应的std:vector (稠密向量)
* Params: v: 转换后的向量
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-17
*/
template<class T>
void SparseVector<T>::toVector(vector<T> & v)const
{
	v.clear();
	v.resize(m_Length, m_ZeroVal);

	for(unsigned i = 0; i < m_Index.size(); ++i)
	{
		v[m_Index[i]] = m_Vec[i];
	}
}

/**
* Function: This function returns the SparseVector's size.
* Params: None
* Return: the SparseVector's size
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
inline unsigned SparseVector<T>::size()const
{
	return m_Length;
}

/**
* Function: Whether the SV is empty.
* Params: None
* Return: empty? true : false
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-20-09.19
*/
template<class T>
inline bool SparseVector<T>::empty()const
{
	return (0 == m_Length);
}

/**
* Function: This function returns the SparseVector's first element.
* Params: None
* Return: the SparseVector's first element.
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
const T & SparseVector<T>::front()const
{
	if(0 == m_Length)
	{
		//cout << "Error: Out Of Range! Empty!" << endl;
		return m_ZeroVal;
	}

	if(m_Index.size() > 0 && m_Index[0] == 0)//如果第0个元素是非零元素
	{
		return m_Vec[0];
	}
	return m_ZeroVal;
}

/**
* Function: This function returns the SparseVector's last element.
* Params: None
* Return: the SparseVector's last element.
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
const T & SparseVector<T>::back()const
{
	if(0 == m_Length)
	{
		//cout << "Error: Out Of Range! Empty!" << endl;
		return m_ZeroVal;
	}

	if(m_Index.size() > 0 && m_Index.back() == m_Length - 1)//如果最后一个元素是非零元素
	{
		return m_Vec.back();
	}
	return m_ZeroVal;
}

/**
* Function: This function returns the SparseVector's index-th element.
* Params: index: the index of the element.
* Return: the SparseVector's index-th element.
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
const T & SparseVector<T>::at(const unsigned index)const
{
	if(index >= m_Length)
	{
		//cout << "Error: Out Of Range!" << endl;
		return m_ZeroVal;
	}

	int i = biSearch(index);
	if(i >= 0 && m_Index[i] == index)
	{
		return m_Vec[i];
	}
	return m_ZeroVal;
}


/**
* Function: num of the not zero elements
* Params:
* Return:
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-23-19.15
*/
template<class T>
inline unsigned SparseVector<T>::nzSize()const
{
	return m_Index.size();
}

template<class T>
inline const unsigned SparseVector<T>::nzIndex(unsigned pos) const
{
	return m_Index[pos];
}

template<class T>
inline const T & SparseVector<T>::nzValue(unsigned pos)const
{
	return m_Vec[pos];
}

/**
* Function: This function clear the SparseVector (remove all the element).
* Params: None
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
inline void SparseVector<T>::clear()
{
	m_Index.clear();
	m_Vec.clear();
	m_Length = 0;
}

/**
* Function: Change the size of the SV, the newly-created elements will be
initialize by the zero element.
* Params: num: the new size.
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
void SparseVector<T>::resize(const unsigned num)
{
	if(num >= m_Length)//增加长度，增加部分用0元素填充。
	{
		m_Length = num;
		return;
	}

	//减小长度，需要删除一些元素
	int i = biSearch(num);
	if(i < 0 || m_Index[i] != num)
	{
		++i;
	}

	//从i-th个元素及之后的元素都删除.
	m_Index.resize(i);
	m_Vec.resize(i);
	m_Length = num;
}


/**
* Function: Append the element v to the end of the SV.
* Params: v
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
void SparseVector<T>::push_back(const T & v)
{
	if(m_ZeroVal != v)
	{
		m_Vec.push_back(v);
		m_Index.push_back(m_Length);
	}
	++m_Length;
}


/**
* Function: Remove the last element.
* Params: None
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
void SparseVector<T>::pop_back()
{
	if(0 == m_Length)
	{
		//cout << "Error: Empty!" << endl;
		return;
	}

	--m_Length;

	if(m_Index.size() > 0 && m_Index.back() == m_Length)//如果最后一个元素是非零元素，则要删除，否则不需要动作。
	{
		m_Vec.pop_back();
		m_Index.pop_back();
	}
}

/**
* Function: Insert the an element to the position pos.
* Params: v
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
void SparseVector<T>::insert(const unsigned pos, const T & v)
{
	if(pos > m_Length)
	{
		//cout << "Error: Out Of Range!" << endl;
		return;
	}

	//如果正好在最后一个位置插入非零元素值
	if(pos == m_Length && v != m_ZeroVal)
	{
		m_Vec.push_back(v);
		m_Index.push_back(m_Length);
		++m_Length;
		return;
	}

	++m_Length;

	//查找插入位置
	int i = biSearch(pos);
	if(i < 0 || m_Index[i] != pos)
	{
		++i;
	}
	//如果插入的是非零元素
	if(v != m_ZeroVal)
	{
		m_Vec.insert(m_Vec.begin() + i, v);
		m_Index.insert(m_Index.begin() + i, pos);
		++i;
	}
	//在插入点之后的元素位置都要加1
	for(; i < m_Index.size(); ++i)
	{
		++(m_Index[i]);
	}
}


/**
* Function: Remove the element which position is pos.
* Params: v
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
void SparseVector<T>::erase(const unsigned pos)
{
	if(pos >= m_Length)
	{
		//cout << "Error : Out Of Range!" << endl;
		return;
	}

	int i = biSearch(pos);
	if(i >= 0 && m_Index[i] == pos)//如果删除位置是一个非零元素
	{
		m_Vec.erase(m_Vec.begin() + i);
		m_Index.erase(m_Index.begin() + i);
	}
	else
	{
		++i;
	}
	//在删除元素位置后的所有元素的位置都要减1
	for(; i < m_Index.size(); ++i)
	{
		--(m_Index[i]);
	}
	--m_Length;
}

/**
* Function: erase the element which subscript from start to end (end is not include)
* Params: start:  end:
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-20-09.19
*/

template<class T>
void SparseVector<T>::erase(const unsigned start, const unsigned end)
{
	if(end > m_Length)
	{
		//cout << "Error : Out Of Range!" << endl;
		return;
	}

	if(start >= end)
	{
		//cout << "Nothing to Erase!" << endl;
		return;
	}

	int i_start = biSearch(start);
	int i_end = biSearch(end);

	if(i_start < 0 || m_Index[i_start] != start)
	{
		++i_start;
	}
	if(i_end < 0 || m_Index[i_end] != end)
	{
		++i_end;
	}

	int eraseLen = (end - start);
	m_Length -= eraseLen;
	if(i_start < i_end)
	{
		m_Index.erase(m_Index.begin() + i_start, m_Index.begin() + i_end);
		m_Vec.erase(m_Vec.begin() + i_start, m_Vec.begin() + i_end);
	}
	for(; i_start < m_Index.size(); ++i_start)
	{
		m_Index[i_start] -= eraseLen;
	}
}


/**
* Function: Set the specific element's value to v.
* Params: pos: the position of the element to be set; v: the new value.
* Return: None
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
void SparseVector<T>::set(const unsigned pos, const T & v)
{
	if(pos >= m_Length)
	{
		//cout << "Error: Out Of Range!" << endl;
		return;
	}

	int i = biSearch(pos);
	if(i >= 0 && m_Index[i] == pos)//如果pos处的元素为非零元素
	{
		if(v != m_ZeroVal)//要设置的元素也是非零的
		{
			m_Vec[i] = v;
			return;
		}

		//0 to not 0/////非零元素变为0元素，只需删除即可
		m_Index.erase(m_Index.begin() + i);
		m_Vec.erase(m_Vec.begin() + i);
	}
	else
	{
		if(v == m_ZeroVal)
		{
			return;
		}

		// not 0 to 0/
		++i;
		m_Vec.insert(m_Vec.begin() + i, v);
		m_Index.insert(m_Index.begin() + i, pos);
	}
}


template<class T>
void SparseVector<T>::update(const unsigned pos, const T & v)
{
	if(pos >= m_Length)
	{
		//cout << "Error: Out Of Range! index:" << pos << " size:" << m_Length << endl;
		return;
	}

	int i = biSearch(pos);
	if(i >= 0 && m_Index[i] == pos)
	{
		m_Vec[i] += v;
		if(m_Vec[i] != m_ZeroVal)
		{
			return;
		}

		m_Index.erase(m_Index.begin() + i);
		m_Vec.erase(m_Vec.begin() + i);
	}
	else
	{
		T tmp = v + m_ZeroVal;
		if(tmp == m_ZeroVal)
		{
			return;
		}

		++i;
		m_Vec.insert(m_Vec.begin() + i, tmp);
		m_Index.insert(m_Index.begin() + i, pos);
	}
}



/**
* Function: 在一个递增的vector中查找一个元素.(二分查找)
* Params: pos: 要查找的元素值
* Return: 不大于pos的最大元素的位置.
*
* Version: 1.0
* Author: lujun
* Time: 2011-12-15
*/
template<class T>
int SparseVector<T>::biSearch(const unsigned pos)const
{
	int max = m_Index.size();
	if(max == 0)
	{
		return -1;
	}

	int min = 0, current;
	--max;
	// Binary search
	while((m_Index[min] <= pos) && (m_Index[max] >= pos))
	{
		current = (max + min) >> 1;
		if(m_Index[current] > pos)
		{
			max = current - 1;
		}
		else if(m_Index[current] < pos)
		{
			min = current + 1;
		}
		else
		{
			return current;
		}
	}
	if(m_Index[max] < pos)
	{
		return max;
	}
	else
	{
		return min - 1;
	}
}


//template<class T>
//int SparseVector<T>::biSearch(const unsigned val)const
//{
//	int top = m_Index.size();
//	if(top == 0)
//		return -1;
//
//	int buttom = 0,mid;
//	--top;
//
//	while(buttom <= top)
//	{
//		mid = (buttom + top) >> 1;
//		if(m_Index[mid] < val)
//			buttom = mid + 1;
//		else if(m_Index[mid] > val)
//			top = mid - 1;
//		else
//			return mid;
//	}
//	return top;
//}

//template<class T>
//int SparseVector<T>::biSearch(const unsigned val)const
//{
//	int top = m_Index.size();
//	if(top==0||m_Index[0]>val)
//		return -1;
//
//	int buttom = 0,mid;
//	while(buttom+1!=top)
//	{
//		mid = (top+buttom)>>1;
//		if(m_Index[mid]>val)
//			top = mid;
//		else
//			buttom = mid;
//	}
//	return buttom;
//}


template<class T>
void SparseVector<T>::self_check()
{
	assert(m_Index.size() == m_Vec.size());

	for(int i = 0; i < m_Vec.size(); i++)
	{
		assert(m_Vec[i] != m_ZeroVal);
	}

	for(int i = 1; i < m_Index.size(); ++i)
	{
		assert(m_Index[i - 1] < m_Index[i]);
	}

	assert(m_Index.size() <= m_Length);

	if(m_Index.size() > 0)
	{
		assert(m_Index.back() <= m_Length);
	}

}

template<class T>
void SparseVector<T>::show()
{
	cout << "s============================" << endl;
	for(int i = 0; i < m_Index.size(); i++)
	{
		cout << m_Index[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < m_Vec.size(); i++)
	{
		cout << m_Vec[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < m_Length; i++)
	{
		cout << at(i) << " ";
	}

	cout << endl;

	cout << "e============================" << endl;
}

